This invention relates in general to computers and in particular, to cache memory.
CPU designers, since the inception of computers, have been driven to design faster and better processors in a cost-effective manner. For example, as faster versions of a particular CPU becomes available, designers will often increase the CPU's clock frequency as a simple and cost effective means of improving the CPU's throughput.
After a certain point, the speed of the system's main memory (input/output) becomes a limiting factor as to how fast the CPU can operate. When the CPU's operating speed exceeds the main memory's operating requirements, the CPU must issue one or more wait states to allow memory to catch up. Wait states, however, have a deleterious effect on CPU's performance. In some instances, one wait state can decrease the CPU's performance by about 20-30%.
Although wait states can be eliminated by employing faster memory, it is very expensive and may be impractical. Typically, the difference between the price of a fast memory chip and the next fastest speed grade can range from 50-100%. Thus, the cost can be quite prohibitive, especially for a system requiring a large memory.
A cost effective solution has been to provide the CPU with a hierarchical memory consisting of multiple levels of memory with different speeds and sizes. Since the fastest memories are more expensive per bit than slower memories, they are usually smaller in size. This smaller memory, referred to as a "cache", is closely located to the microprocessor or even integrated into the same chip as the microprocessor.
Conceptually, the memory controller retrieves instructions and data that are currently used by the processor and stores them into the cache. When a processor fetches instructions or data, it first checks the cache. The control logic determines if the required information is stored in the cache (cache hit). If a cache hit occurs, the CPU does not need to access to main memory. The control logic uses valuable cycles to determine if the requested data is in the cache. However, this cost is acceptable since accesses to main memory is much slower.
As can been seen, the higher the cache "hit" rate is, the faster the CPU can perform its duties. obviously, the larger the cache, the more data it can store, and thus, a higher probability of a hit. However, in the real world, microprocessor designers are always faced with size constraints due to the fact that there is limited available space on a die. Using a larger die size, although effective, is not practical since the cost increases as die size increases. Further, reducing the size of the cache without reducing the performance allows the designer to improve the performance of other functional units of the CPU.
Thus, there is a need for designing a cache that can determine if a hit has occurred using a minimum number of cycles and a high hit rate while reducing space needed on the chip.